In Infrastructure-as-a-Service (IaaS) cloud service model, users can obtain on-demand resources by rapid provisioning of virtual machines (VMs). VMs of one user are typically co-located with VMs of another user on a physical host, especially in a public cloud. Each identically configured VM is expected to receive similar performance for central processing unit (CPU), memory, disk input/output (I/O), and network bandwidth regardless of its location in the cloud (that is, the physical machine on which the VM is placed). However, such services do not necessarily provide performance guarantees. In practice, the performance of a VM depends on the underlying hardware, how the hardware is configured, and the amount of shared resources consumed by its co-located virtual machines. As workloads have different resource requirements, it is possible that an insufficient host for one VM can be sufficient for another VM, and swapping the locations of the two VMs may even improve the performance (or other metrics) of both VMs. However, in existing approaches, cloud providers do not offer a VM swapping service.